package com.sh.algorithm.easy;

/**
 * @author veviz
 * @description
 * 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
 *
 * 给定一个数字 n，找出可形成完整阶梯行的总行数。
 *
 * n 是一个非负整数，并且在32位有符号整型的范围内。
 *
 * 示例 1:
 *
 * n = 5
 *
 * 硬币可排列成以下几行:
 * ¤
 * ¤ ¤
 * ¤ ¤
 *
 * 因为第三行不完整，所以返回2.
 *
 * 示例 2:
 *
 * n = 8
 *
 * 硬币可排列成以下几行:
 * ¤
 * ¤ ¤
 * ¤ ¤ ¤
 * ¤ ¤
 *
 * 因为第四行不完整，所以返回3.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/arranging-coins
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @create 2020-03-02 21:38
 */
public class Solution441 {

    /**
     * 用数学公式，每一列的值放在一起，就是一个等差数列
     * (1+k)k/2 < n => k<sqrt(2*n+1/4)-1/2
     * 担心2*n会超过sqrt的最大值，我们将2提出来，变为sqrt(2)*sqrt(n+1/8)-1/2
     * @param n
     * @return
     */
    public int arrangeCoinsNew(int n){
        return (int)(Math.sqrt(2)*Math.sqrt(n+0.125)-0.5);
    }


    public static int arrangeCoins(int n) {
        if (n < 1){
            return 0;
        }
        int i = 1;
        while (n > 0){
            n = n - i;
            if (n < i+1){
                break;
            }
            i++;
        }
        return i;
    }

    public static void main(String[] args) {
        System.out.println(arrangeCoins(5));
    }
}
